package main

import "fmt"

func main() {
	// 最大子序列的和
	var a []int = []int{1, 2, 34, 4, -10, 5, 6, 6, -4, 8, -33, 9}
	var max1 = maxSumRec(a, 0, len(a)-1)
	fmt.Println(max1)
}

func maxSumRec(a []int, left, right int) int {
	if left == right {
		if a[left] > 0 {
			return a[left]
		} else {
			return 0
		}
	}
	center := (left + right) / 2
	maxLeftSum := maxSumRec(a, left, center)
	maxRightSum := maxSumRec(a, center+1, right)
	maxLeftBorderSum, leftBorderSum := 0, 0
	for i := center; i >= left; i-- {
		leftBorderSum += a[i]
		if leftBorderSum > maxLeftBorderSum {
			maxLeftBorderSum = leftBorderSum
		}
	}
	maxRightBorderSum, rightBorderSum := 0, 0
	for i := center + 1; i <= right; i++ {
		//for i := right; i >= center+1; i-- {
		rightBorderSum += a[i]
		if rightBorderSum > maxRightBorderSum {
			maxRightBorderSum = rightBorderSum
		}
	}
	return max(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum)

}
